package homeword;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

public class Quicksort {

    public static void main(String[] args) {
        Random random = new Random();
        //随机生成1~1000000的数
        int[] ints = random.ints(1000000, 1, 1000000)
                .toArray();
        int[] arr1 = Arrays.copyOf(ints, ints.length);
        int[] arr2 = Arrays.copyOf(ints, ints.length);

        quicksort_1(arr1);
        str(arr2);
    }

    /**
     * 插入排序
     */
    public static void str(int[] arr){
        for (int i =1; i < arr.length;i++){
            int j = i;
            int king = arr[j];
            for ( ; j > 0 && king < arr[j-1];j--)
                arr[j] = arr[j-1];
            arr[j] = king;
        }
    }

    private static void quicksort_1(int[] arr){
        long begin = System.currentTimeMillis();
        quicksort(arr,0,arr.length-1);
        long end = System.currentTimeMillis();

        System.out.println("快速耗时：" + (end - begin));
    }

    public static void quicksort(int[] arr, int left, int right){
        if (left < right) {
            int index = getIndex(arr,left,right);

            quicksort(arr,left,index-1);
            quicksort(arr,index+1,left);
        }
    }

    private static int getIndex(int[] arr, int left, int right) {
        int temp = arr[left];

        while (left < right){
            while (left < right && temp <= arr[right])
                right--;
            arr[left] = arr[right];

            while (left < right && temp >= arr[left])
                left++;
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }
}
